from queue import Queue

from bank.Bank import Bank
from bank.BoatPosition import BoatPosition
from tree.Tree import Tree
from tree.TreeNode import TreeNode


def _is_nodes_equal(node1: TreeNode, node2: TreeNode):
    if node1 is None or node2 is None:
        return False

    return node1.left.savage == node2.left.savage \
           and node1.left.preacher == node2.left.preacher \
           and node1.right.savage == node2.right.savage \
           and node1.right.preacher == node2.right.preacher and \
           node1.boat_position == node2.boat_position


class CrossRiverManager:

    def __init__(self, number, boat):
        self.number = number
        self.boat = boat

    def cross_river(self):
        tree = self._build_state_tree()
        solution = 0

        while True:
            final_node = tree.DFS()
            if final_node is None:
                break

            path = tree.trace(final_node)
            if path is not None:
                solution += 1
                print('\nsolution' + str(solution) + ':')
                for node in path:
                    node.print_state()

        if solution == 0:
            print('no solution')

    def _build_state_tree(self):
        left = Bank(self.number, self.number)
        right = Bank()
        root = TreeNode(left, right, boat_position=BoatPosition.LEFT)
        tree = Tree(root, self.number)
        queue = Queue()
        queue.put(root)

        is_root_node = True
        while not queue.empty():
            node: TreeNode = queue.get()
            if not is_root_node:
                tree.add_node(node)
            else:
                is_root_node = False
            if node.is_leaf_node(self.number):
                return tree

            for delta_savage in range(0, self.boat + 1):
                for delta_preacher in range(0, self.boat + 1):
                    if 0 < delta_savage + delta_preacher <= self.boat:
                        boat_position = node.boat_position
                        if boat_position == BoatPosition.LEFT:
                            temp1_node = TreeNode(Bank(node.left.preacher, node.left.savage),
                                                  Bank(node.right.preacher, node.right.savage),
                                                  boat_position=boat_position)
                            can_move_left = temp1_node.left.move(temp1_node.right, self.boat, delta_preacher,
                                                                 delta_savage)
                            if can_move_left and not _is_nodes_equal(temp1_node, node.parent):
                                temp1_node.parent = node
                                temp1_node.reverse_boat_position()
                                node.add_child(temp1_node)

                        elif boat_position == BoatPosition.RIGHT:
                            temp2_node = TreeNode(Bank(node.left.preacher, node.left.savage),
                                                  Bank(node.right.preacher, node.right.savage),
                                                  boat_position=boat_position)
                            can_move_right = temp2_node.right.move(temp2_node.left, self.boat, delta_preacher,
                                                                   delta_savage)
                            if can_move_right and not _is_nodes_equal(temp2_node, node.parent):
                                temp2_node.parent = node
                                temp2_node.reverse_boat_position()
                                node.add_child(temp2_node)

            for child in node.children:
                queue.put(child)

        return tree
